package com.liunian.algorithmstudy.stackandqueue;

import java.util.Deque;
import java.util.LinkedList;

public class MaxSlidingWindow {

    public int[] maxSlidingWindow(int[] nums, int k) {
        int n = nums.length;
        Deque<Integer> deque = new LinkedList<>();
        for (int i = 0; i < k; i++) {
            push(deque, nums[i]);
        }
        int[] res = new int[n - k + 1];
        res[0] = getMaxValue(deque);
        for (int i = k; i < n; i++) {
            pop(deque, nums[i - k]);
            push(deque, nums[i]);
            int maxValue = getMaxValue(deque);
            res[i - k + 1] = maxValue;
        }
        return res;
    }

    private void push(Deque<Integer> deque, int val) {
        while (!deque.isEmpty() && deque.peekLast() < val) {
            deque.pollLast();
        }
        deque.addLast(val);
    }

    private void pop(Deque<Integer> deque, int val) {
        if (!deque.isEmpty() && deque.peekFirst() == val) {
            deque.pollFirst();
        }
    }

    private int getMaxValue(Deque<Integer> deque) {
        return deque.peekFirst();
    }

    public static void main(String[] args) {
        MaxSlidingWindow window = new MaxSlidingWindow();
        window.maxSlidingWindow(new int[] {1,3,-1,-3,5,3,6,7}, 3);
    }

}
